package 题目集.倍增算法.lca;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

//https://www.luogu.com.cn/problem/P3379
public class ch01_朴素算法 {
    // 定义最大节点数和最大深度
    static int MAXN = 500010;
    static int MAXM = 20;
    // 定义节点深度数组
    static int[] depth = new int[MAXN];
    // 定义父节点数组
    static int[]parent = new int[MAXN];
    // 定义图的邻接表表示
    static List<Integer>[] graph = new ArrayList[MAXN];

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        // 读入节点数和查询数
        int n = sc.nextInt();
        int m = sc.nextInt();
        // 读入根节点
        int root = sc.nextInt();

        // 初始化邻接表
        for (int i = 1; i <= n; i++) {
            graph[i] = new ArrayList<>();
        }

        // 读入边
        for (int i = 1; i < n; i++) {
            int u = sc.nextInt();
            int v = sc.nextInt();
            graph[u].add(v);
            graph[v].add(u);
        }

        // 深度优先搜索，预处理出每个节点的深度和父节点
        dfs(root, 0);

        // 处理查询
        for (int i = 1; i <= m; i++) {
            int u = sc.nextInt();
            int v = sc.nextInt();
            System.out.println(lca(u, v));
        }
    }

    // 深度优先搜索函数
    static void dfs(int u, int fa) {
        // 计算节点 u 的深度
        depth[u] = depth[fa] + 1;
        // 计算节点 u 的直接父节点
        parent[u] = fa;
        // 遍历节点 u 的所有子节点
        for (int v : graph[u]) {
            if (v != fa) {
                dfs(v, u);
            }
        }
    }

    // LCA 函数，返回节点 u 和节点 v 的最近公共祖先
    static int lca(int u, int v) {
        // 如果节点 u 的深度小于节点 v 的深度，交换 u 和 v
        if (depth[u] < depth[v]) {
            int tmp = u;
            u = v;
            v = tmp;
        }
        // 使节点 u 和节点 v 移动到同一深度
        int pos = depth[u] - depth[v];
        for (int i = 0; i < pos; i++) {
            u = parent[u];
        }
        while (u != v) {
            u = parent[u];
            v = parent[v];
        }
        return u;
    }
}
